最长递增子序列（LCS）

[编程题]最长递增子序列（LCS）

热度指数：2413 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

给定一个序列 An = a1 ,a2 , ... , an ，找出最长的子序列使得对所有 i < j ，ai < aj 。求出这个子序列的长度

输入描述:

输入的序列

输出描述:

最长递增子序列的长度

示例1

输入

1 -1 2 -2 3 -3 4

输出

算法知识视频讲解

JavaScript V8

A-Kai

const str = readline();
const list = str.split(' ').map(i=>parseInt(i))
let max = 0
// 1.长度为1直接就是1
if(list.length===1){
    max = 1
}else{
// 2. 否则需要处理
    for(let i=0,l=list.length;i<l;i++){
    let tempList = [] // 存储不连续的递增序列
    let index = 1 // 标记从1开始
    for(let j=i;j<l;j++){
        if(tempList.length){
            // 从1开始比较
            if(tempList[index] < list[j]){
                tempList.push(list[j])
                index++
            }
        }else{
            // 发现2个递增的直接存储 下次则从index为1开始比较
            if(list[i] < list[j]){
            tempList.push(list[i])
            tempList.push(list[j])
          }
        }
    }
    if(tempList.length >= max ){
        max = tempList.length
    }
    index = 1
 }
}
print(max)

发表于 2022-09-16 14:52:59 回复(0)